package com.linyaonan.leetcode.sword_to_offer._33;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *
 *  
 *
 * 参考以下这颗二叉搜索树：
 *
 *      5
 *     / \
 *    2   6
 *   / \
 *  1   3
 * 示例 1：
 *
 * 输入: [1,6,3,2,5]
 * 输出: false
 * 示例 2：
 *
 * 输入: [1,3,2,6,5]
 * 输出: true
 *  
 *
 * 提示：
 *
 * 数组长度 <= 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 思路：二叉搜索树的后序遍历结果为[左树][右树]中间节点，并且左树均小于中间节点，右树均大于中间节点
     * @param postorder
     * @return
     */
    public boolean verifyPostorder(int[] postorder) {
        try {
            isBT(postorder, 0, postorder.length - 1);
        } catch (Exception e) {
            return false;
        }
        return true;
    }

    private void isBT(int[] org, int s, int e) throws Exception {
        if (s >= e) {
            return;
        } else {
            int root = org[e];
            int le = e - 1;
            int rs = e;
            for (int i = s; i < e; i++) {
                if (org[i] < root) {
                    le = i;
                } else {
                    rs = i;
                    break;
                }
            }

            for (int i = rs; i < e; i++) {
                if (org[i] <= root) {
                    throw new RuntimeException("error");
                }
            }

            isBT(org, s, le);
            isBT(org, rs, e - 1);
        }
    }
}